// 给你两个单词 word1 和 word2，
// 请返回将 word1 转换成 word2 所使用的最少操作数。
// 你可以对一个单词进行如下三种操作：
// 插入一个字符
// 删除一个字符
// 替换一个字符
// 来源：力扣（LeetCode）
// 链接：https://leetcode.cn/problems/edit-distance
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
  const len1 = word1.length
  const len2 = word2.length
  // 返回 word1 和 word2 的最小编辑距离
  const dp = new Array(len1 + 1).fill(0).map(() => new Array(len2 + 1).fill(0))

  for (let i = 0; i <= len1; i++) {
    dp[i][0] = i
  }
  for (let i = 0; i <= len2; i++) {
    dp[0][i] = i
  }

  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]
      } else {
        dp[i][j] = Math.min(
          dp[i - 1][j] + 1, // 删除 word1[i]
          dp[i][j - 1] + 1,       // 删除 word2[j]
          dp[i - 1][j - 1] + 1    // 替换 word1[i] word2[j] 的字符
        )
      }
    }
  }

  return dp[len1][len2]
}

console.log(
  minDistance('ros', 'horse')
)
